进程管理-死锁

死锁的概念

1. 死锁的定义
   多个进程因为竞争资源和造成的一种相互等待的现象
2. 死锁产生原因
   • 系统资源竞争
   • 进程推进顺序非法
3. 死锁产生的必要条件
   • 互斥条件
   • 不剥夺条件
   • 请求和饱和条件
   • 循环等待条件

死锁的处理策略

1. 预防死锁：破坏死锁产生的四个必要条件中的一个或多个
2. 避免死锁：防止系统进入不安全状态
3. 死锁检测和解除：不采取限制，检测到再解除

死锁避免

1. 系统安全状态
   系统按照某种进程推进顺序（P1,P2,…,Pn),为每个进程Pi分配其所需资源，直到满足每个进程的最大资源需求，使每个进程都可以顺利完成，此时称P1,P2,…,Pn为安全序列，如果系统无法找到一个安全序列，则称系统处于不安全状态。
2. 银行家算法
   银行家算法是最著名的死锁避免算法。
   1. 数据结构描述
      • 可利用资源矢量Available：Available[i]=K表示系统现有Ri类资源K个
      • 最大需求矩阵Max：Max[i,j]=K，表示进程i需要Rj类资源的最大数目为K
      • 分配矩阵Allocation：Allocation[i,j]=K ,表示进程i已经分配到了Rj类资源数目为K
      • 需求矩阵Need：Need[i,j]=K，表示进程i还需要Rj类资源数目为K
   2. 算法描述
   3. 安全性算法

死锁检测和解除

1. 资源分配图
   请求边，分配边

2. 死锁定理
   S为死锁的条件是当且仅当S状态的资源分配图是不可完全化简的。
   资源分配图化简：

3. 死锁解除

   • 资源剥夺法
   • 撤销进程法
   • 进程回退法